The present invention relates to a binary data compression and expansion processing apparatus which can perform high-speed expansion processing of binary data and, more particularly, can perform parallel pipeline processing of the binary data by a two-dimensional coding method.
As a method for compressing and expanding binary data, coding methods, such as the MH method, the MR method, and the M.sup.2 R method, recommended by the CCITT, are internationally standardized, and are widely adopted. Among the three coding methods, i.e., the MH, MR, and M.sup.2 R methods, the M.sup.2 R method has the highest image compression efficiency.
The M.sup.2 R method is well known as a coding method for Group IV facsimile systems. In this method,
a. an End-Of-Line (EOL) code is omitted, PA1 b. a k parameter is set to be infinite, and PA1 c. all the bits of a reference line at the beginning of a page represent white pixels. PA1 a. decoding processing of code PA1 b. generation processing of image data for the decoded code PA1 a. image data on a reference line is scanned to detect the position of point b1, PA1 b. b1+.delta.=a1, and PA1 c. a run length is calculated by (a1-a0=run length), and image data is generated in correspondence with the calculated run length. Therefore, the generation processing of operations (a) to (c) must be sequentially performed in this order, resulting in a low expansion processing speed. To prevent this problem, it is necessary that the operations (a) to (c) are performed substantially simultaneously.
With these assumptions, a data compression ratio can be improved over that of the MR method. If a transmission error, if any, occurs, the error is sequentially transmitted to subsequent scanning lines as a principal problem. In order to prevent this, one-dimensional coding scanning lines are inserted in compression processing. The k parameter is the number of two-dimensional coding scanning lines between these one-dimensional coding scanning lines.
A conventional binary data compression and expansion processing apparatus was realized in software, using a general-purpose microcomputer in order to perform expansion processing of encoded data according to these methods. In this processing, there is no problem when such an apparatus is applied to a facsimile system whose data transmission rate is limited to 9600 bps. However, when the conventional apparatus is used to display image data on work stations of a computer system, a good man-machine interface, for example, a page response time of 1/2 sec or less, cannot be achieved. Therefore, when the sequential expansion processing is executed in accordance with the M.sup.2 R method, the operating speed is considerably reduced, when compared with the MH method.
One cause of the above problem lies in the processing method of the entire system. More specifically, in a conventional system, decoding is performed in a bit serial manner. In order to solve the problem, parallel processing, advanced processing, and pipeline processing are widely utilized. The binary image data expansion processing can be apparently divided into:
Therefore, decoding and generation processing can be parallel-performed by separate hardware arrangements. In such arrangements, while a code is expanded, the next code is decoded, and the entire processing can be then pipelined. When binary data encoded by MH and MR methods is expanded, there is no problem in the advanced processing. However, the M.sup.2 R method has the following problems.
In all the MH, MR, and M.sup.2 R methods, the starting run of each line is always a white run and must be decoded to be white pixels. In the case of the MH and MR methods, an EOL code is used. Therefore, a decoding processing section which performs the advanced processing can detect the beginning of the next line due to the presence of an EOL code, regardless of progress of generation processing by a generation processing section.
However, since there is no EOL code in the M.sup.2 R method, the beginning of the next line can only be detected when the generation processing section develops each code and reaches an end of line. Therefore, if the beginning of the next line is indeterminate, it cannot be determined if the color of this portion is forcibly determined as white.
As a result, a decoding operation of a horizontal mode using separate code tables for a white run and a black run cannot be started in an advanced manner. More specifically, in the expansion processing of the M.sup.2 R method of a conventional apparatus, the advanced processing cannot be effectively performed.
Furthermore, when deviation .delta. of point a1 is detected by the advanced decoding processing, generation processing of two-dimensional code data encoded by the MR or M.sup.2 R method is conventionally realized as follows: